# -*- encoding: utf-8 -*-
'''
@文件    :mysqrt.py
@说明    :实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

本题采用二分法取中位数后求整进行计算
涉及关键点： 上界下界的设定和根据是否满足平方数条件而进行对应调整
python除法取整的操作 //

@时间    :2020/06/01 17:00:38
@作者    :张钧铭
'''

class Solution(object):
    def mySqrt(self, x: int) -> int:
        """
        :type x: int
        :rtype: int
        """

        left,right,ans = 0,x,-1
        while left <= right:              #下界最终等于或者超过上界，则结束
            mid = (left + right) // 2
            if mid * mid <= x:
                ans = mid                 
                left = mid + 1         #小了，则调整下届，中点加一，排除了中点的剩余部分
            else:
                right = mid - 1
        return ans

s=Solution()
s.mySqrt(100)


